A Sort Of A Blog
旧游无处不堪寻,无寻处,惟有少年心
『计算机的组成与设计』-指令:计算机的语言

当你的噩梦里再也没有恶龙和沼泽,而全都是生活难题的那一刻,你就知道你长大了。

计算机语言中的基本单词称为指令。一台计算机的全部指令称为该计算机的指令集
尽管机器语言种类繁多,但他们之间十分相似,其差异性更像人类语言的”方言”。
本篇讲解 MIPS 指令集。

  1. Intel x86,在 PC 以及后 PC 时代的云计算领域占统治地位
  2. ARMv8 将 ARMv7 的地址范围从 32 位扩展到 64 位。讽刺的是,ARMv8 更接近 MIPS 而非 ARMv7

注意: MIPS 和 RAM 属于精简指令集(Reduced Instruction Set Computer,RISC),而 x86 属于复杂指令集(Complex Instruction Set Computer,CISC)。
现在在 RISC 占统治地位的是 RAM,在 CISC 占统治地位的是 x86。MIPS 已死,MIPS 永生。
以 MIPS 为代表的精简指令集关注的是:

  • 减少指令的类型
  • 降低指令复杂度

基本原则: a simple CPU is a faster CPU。

MIPS 操作数


名字 示例 注释
32 个寄存器 $s0-$s7,$t0-$t9,$zero,$a0-$a3,
$v0-$v1,$k0-$k1,$gp,$fp,$sp,
$ra,$at
寄存器用于数据的快速存取,在 MIPS 中,只能对放在寄存器中的数据执行算术操作,寄存器 $zero 恒为 0,$at 被汇编器保留,处理大常数。
232 个存储器字 Memory[0],Memory[4],…,
Memory[4294967292]
存储器只能通过数据传输指令访问。MIPS 使用字节编址,所以连续字地址相差 4

MIPS 寄存器字解释

编号 名称 用途
0 $zero The Constant Value 0
1 $at Assembler Temporary
2-3 $v0-$v1 Values of Function Results and Expression Evaluation
4-7 $a0-$a3 Arguments
8-15 $t0-$t7 Temporaries
16-23 $s0-$s7 Saved Temporaries
24-25 $t8-$t9 Temporaries
26-27 $k0-$k1 Reserved of OS Kernel
28 $gp Global Pointer
29 $sp Stack Pointer
30 $fp Frame Pointer
31 $ra Return Address

MIPS 指令


算术指令

指令 示例 含义 注释
加法 add $s1, $s2, $s3 $s1 = $s2 + $s3 三个寄存器操作数
减法 sub $s1, $s2, $s3 $s1 = $s2 - $s3 三个寄存器操作数
立即数加法 addi $s1, $s2, 20 $s1 = $s2 + 20 用于加常数数据

数据传输指令

指令 示例 含义 注释
取字 lw $s1, 20($s2) $s1 = Memory[$s2 + 20] 将一个字从内存中取到寄存器
存字 sw $s1, 20($s2) Memory[$s2 + 20] = $s1 将一个字从寄存器中存到内存
取半字 lh $s1, 20($s2) $s1 = Memory[$s2 + 20] 将半个字从内存中取到寄存器
存半字 sw $s1, 20($s2) Memory[$s2 + 20] = $s1 将半个字从寄存器中存到内存
取无符号半字 lhu $s1, 20($s2) $s1 = Memory[$s2 + 20] 将半个字从内存中取到寄存器
取字节 lb $s1, 20($s2) $s1 = Memory[$s2 + 20] 将一个字节从内存中取到寄存器
存字节 sb $s1, 20($s2) Memory[$s2 + 20] = $s1 将一个字节从寄存器中存到内存
取无符号字节 lbu $s1, 20($s2) $s1 = Memory[$s2 + 20] 将一个字节从内存中取到寄存器
取链接字 ll $s1, 20($s2) $s1 = Memory[$s2 + 20] 取字作为原子交换的前半部分
存条件字 sc $s1, 20($s2) Memory[$s2 + 20] = $s1;
$s1 = 0 or 1
存字作为原子交换的后半部分
取立即数高位 lui $s1, 20 $s1 = 20 * 216 取立即数并放在高16位

位操作

指令 示例 含义 注释
and $s1,$s2,$s3 $s1 = $s2 & $s3 三个寄存器操作数按位与
or $s1,$s2,$s3 $s1 = $s2 | $s3 三个寄存器操作数按位或
或非 nor $s1,$s2,$s3 $s1 = ~($s2 | $s3) 三个寄存器操作数按位或非
立即数与 andi $s1,$s2,20 $s1 = $s2 & 20 和常数按位与
立即数或 ori $s1,$s2,20 $s1 = $s2 | 20 和常数按位或
逻辑左移 sll $s1,$s2,10 $s1 = $s2 << 10 根据常数左移相应位
逻辑右移 srl $s1,$s2,10 $s1 = $s2 >> 10 根据常数右移相应位

条件分支

指令 示例 含义 注释
相等时跳转 beq $s1,$s2,25 if($s1 == $s2) go to PC + 4 + 100 相等检测,和 PC 相关的跳转
不相等时跳转 bne $s1,$s2,25 if($s1 != $s2) go to PC + 4 + 100 不相等检测,和 PC 相关的跳转
小于时置位 slt $s1,$s2,$s3 if($s2 < $s3) $s1 = 1; else $s1 = 0 比较是否小于
无符号数比较小于时置位 sltu $s1,$s2,$s3 if($s2 < $s3) $s1 = 1; else $s1 = 0 比较是否小于无符号数
无符号数比较小于立即数时置位 slti $s1,$s2,20 if($s2 < 20) $s1 = 1; else $s1 = 0 比较是否小于常数
无符号数比较小于无符号立即数时置位 sltiu $s1,$s2,20 if($s2 < 20) $s1 = 1; else $s1 = 0 比较是否小于无符号常数

无条件跳转

指令 示例 含义 注释
跳转 j 2500 goto 10000 跳转到目标地址
跳转至寄存器所指地址 jr $ra go to $ra 用于 switch 语句以及过程调用
跳转并链接 jal 2500 $ra = PC + 4; go to 10000 用于过程调用

MIPS 指令的特点


  1. 固定的指令长度(32-bit 即1 word)
    简化了从存储器取指令。
  2. 简单的寻址模式
    简化了从存储器取操作数。
  3. 指令数量少,功能简单
    简化指令的执行过程。
  4. 只有 load 和 store 指令能访问存储器

硬件设计三原则:


任何计算机必须能执行算术运算。 MIPS 汇编语言使用 add a, b, c 表示将 b 和 c 相加的结果赋值给 a。
与加法类似的指令一般都有三个操作数: 两个进行运算的数和一个保存结果的数。
这种情况说明了硬件设计的三条基本原则的第一条:
设计原则1: 简单源于规整
MIPS 算术运算指令的操作数有严格限制。他们必须来自寄存器。MIPS 体系结构中寄存器的大小为 32 个,因此在 MIPS 体系结构中将其称为字 word
高级语言中的变量与寄存器的一个主要区别就是寄存器的数量有限。
寄存器个数限制为 32 个的理由可表示为硬件设计的三条基本原则的第二条:

设计原则2: 越小越快
大量的寄存器可能会使时钟周期变长,因为电信号传输更远的距离必然花费更多时间。

设计原则3: 优秀的设计需要折中的方案
MIPS 设计者为保持所有指令长度相同,采用了一种折中方案: 不同类型的指令采用不同的指令格式。

在高级语言中,有保存仅含一个数据的简单变量。也有像数组或结构那样的复杂数据结构。处理器只将少量数据保存在寄存器中,数据结构是存放在存储器中的。
并且之前说过,MIPS 的算术运算只能对寄存器进行操作,因此,MIPS 必须包含在存储器和寄存器之间传送数据的指令。这些指令称为数据传送指令
为了访问存储器中的一个字,指令必须给出存储器地址(address)。
将数据从储存器复制到寄存器的数据传输指令称为取数(load)指令。取数指令的格式是操作码之后接着目标寄存器,在后面是用来访问存储器的常数和寄存器。常数和第二个寄存器中的值相加即得到存储器地址。取数指令助记符为 lw(load word)。
数据传输指令的常数称为偏移量(offset),存放基址的寄存器称为基址寄存器(base register)。
与取数对应的指令称为存数 store word
有一个常数操作数的快速加法指令称为加立即数(add immediate,addi)。MIPS 支持负常数,因此不需要设置减立即数指令。

示例:

假设

  • A 是一个 100 个字的数组,首地址在寄存器 $19 中
  • 变量 h 对应寄存器 $18
  • 临时数据存储在寄存器 $8

那么
A[10] = h + A[3]对应的 MIPS 指令是:

lw $8, 12($19)
add $8, $18, $8
sw $8, 40($19)

MIPS 指令的基本格式


指令的布局形式叫做指令格式

注意:

  • 在 R 型指令中,rd 表示用于存放结果的目的操作数,rs 表示第一个源操作数,rt 表示第二个源操作数
  • 在 I 型指令中,rt 表示接收取数结果的目的操作数,rs 表示源操作数

R 型指令示例

如: lw rd, rs, rt

add $8, $9, $10

查指令编码表可得:
opcode: 0, funct 32, shamt: 0(非移位指令)
根据操作数可得:
rd = 8(目的操作数), rs = 9(第一个源操作数), rt = 10(第二个源操作数)
所以 R 指令为:
000000 01001 01010 01000 00000 100000

sll $t2, $s0, 4

查指令编码表可得:
opcode: 0, funct 0, shamt(shift amount): 4
根据操作数可得:
rd = 10(目的操作数), rs = 0(第一个源操作数), rt = 16(第二个源操作数)
所以 R 指令为:
000000 00000 10000 01010 00100 000000

I 型指令示例

如: addi rt, imm(rs)

addi $21, $22, -50

查指令编码表可得:
opcode: 8
分析指令可得:
rs = 22, rt = 21, imm = -50
所以 I 指令为:
001000 10110 10101 1111111111001110

决策指令


程序语言通常使用if语句描述决策,有时也使用 go to 语句和标签。
MIPS 汇编语言中有两条类似 if 和 go to 语句功能的指令:

  1. beq reg1, reg2, L1
    该指令表示: 如果 reg1 与 reg2 中的数值相等,则跳转标签为 L1 的语句执行。

beq(branch if equal)表示如果相等则分支
2. bne reg1, reg2, L1
该指令表示: 如果 reg1 与 reg2 中的数值不相等,则跳转标签为 L1 的语句执行。
bne(branch if not equal)表示如果不相等则分支

这两条指令称为条件分支指令 conditional branch。指该指令先比较两个值,根据比较的结果决定是否从程序中的一个新地址开始执行指令序列。

还有另一种分支指令,称为无条件分支指令 unconditional branch。当遇到这种指令,程序必须分支。MIPS 将该指令命名为 j 意为 jump。

循环

无论是 if 语句,还是循环语句,决策起着重要作用,这两种情况,决策的汇编指令是相同的。

while (save[i] == k)
i += 1;

假设 i 和 k 保存在$s3和$s5中,save 数组基址为$s6,将上述代码转为 MIPS 汇编。

Loop: sll $t0, $s3, 2
add $t0, $t0, $s6
bne $t0, $s5 Exit
add $s3, $s3, 1
j Loop
Exit:

case/switch 语句

大多数程序设计语言都有 case/switch 语句,使得程序员可以根据某个变量的值选择不同的分支。
实现方式是: 将多个指令序列分支的地址编码为一张表,即转移表(jump table)
MIPS 提供了寄存器跳转指令 jr 意为 jump register,用来无条件跳转到寄存器的指定的地址。

计算机硬件对过程的支持


过程(procedure)或函数是程序员进行结构化编程的工具,两者有助于提高程序的可理解性和代码的可重用性。
MIPS 在为过程调用分配寄存器时遵循下述约定:

  • $a0-$a3: 用于传递参数的 4 个参数寄存器
  • $v0-$v1: 用于返回值的两个值寄存器
  • $ra: 用于返回起始点的返回地址寄存器

除了分配这些寄存器之外,MIPS 还包括一条过程调用指令: 跳转到某个地址的同时将下一条指令的地址保存在 $ra 中,这条跳转和链接指令(jump and link instruction)格式为:
jal procedureAddress
在存储程序概念中,使用一个寄存器保存当前运行的指令地址是决定必要的。这个寄存器称为程序计数器(program counter),在 MIPS 中简称 PC。jal 指令实际将 PC+4 保存在 $ra 中。

使用更多的寄存器

换出寄存器最理想的数据结构是栈(stack): 一种后进先出的队列。
栈需要一个指针指向栈中最新分配的地址,以指示下一个过程置换出寄存器的位置。或是寄存器旧值的存放位置。在每次寄存器进行保存或恢复时,栈指针(stack pointer)以字为单位进行调整。
MIPS 为栈指针准备了第 29 号寄存器 $sp。
将数据放入栈中的操作称为 push。
从栈中移除数据的操作称为 pop。